/*
 * @lc app=leetcode.cn id=16 lang=cpp
 *
 * [16] 最接近的三数之和
 */

// @lc code=start
class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());

        int delta = INT_MAX;
        for (int i = 0; i < nums.size(); i++) {
            if (delta == 0)
                break;

            int l = i + 1, r = nums.size() - 1;

            while (l < r) {
                int t = nums[i] + nums[l] + nums[r] - target;
                delta = std::abs(delta) < std::abs(t) ? 
                    delta : t;

                if (delta == 0)
                    break;

                if (t < 0)
                    l++;
                
                else
                    r--;
            }
        }

        return target + delta;
    }
};
// @lc code=end

